import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/9 9:23
 * @description 深度优先遍历
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode t = new TreeNode(val);
            t.left = root;
            return t;
        }
        insert(val, root, 1, depth);
        return root;
    }
    public void insert(int val, TreeNode node, int depth, int n) {
        if (node == null) {
            return;
        }
        if (depth == n - 1) {
            TreeNode t = node.left;
            node.left = new TreeNode(val);
            node.left.left = t;
            t = node.right;
            node.right = new TreeNode(val);
            node.right.right = t;
        }else {
            insert(val, node.left, depth + 1, n);
            insert(val, node.right, depth + 1, n);
        }
    }
}
